Scheduling parallel machines with inclusive processing set restrictions and job rejection

In this article, we study a parallel machine scheduling problem with inclusive processing set restrictions and the option of job rejection. In the problem, each job is compatible to a subset of machines, and machines are linearly ordered such that a higher‐indexed machine can process all those jobs that a lower‐indexed machine can process (but not conversely). To achieve a tight production due date, some of the jobs might be rejected at certain penalty. We first study the problem of minimizing the makespan of all accepted jobs plus the total penalty cost of all rejected jobs, where we develop a ‐approximation algorithm with a time complexity of . We then study two bicriteria variants of the problem. For the variant problem of minimizing the makespan subject to a given bound on the total rejection cost, we develop a ‐approximation algorithm with a time complexity of . For the variant problem of maximizing the total rejection cost of the accepted jobs subject to a given bound on the makespan, we present a 0.5‐approximation algorithm with a time complexity of . © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 667–681, 2017     

Aggregating courier deliveries

We consider the problem of efficiently scheduling deliveries by an uncapacitated courier from a central location under online arrivals. We consider both adversary‐controlled and Poisson arrival processes. In the adversarial setting we provide a randomized (3βΔ/2δ ? 1) ‐competitive algorithm, where β is the approximation ratio of the traveling salesman problem, δ is the minimum distance between the central location and any customer, and Δ is the length of the optimal traveling salesman tour overall customer locations and the central location. We provide instances showing that this analysis is tight. We also prove a 1 + 0.271Δ/δ lower‐bound on the competitive ratio of any algorithm in this setting. In the Poisson setting, we relax our assumption of deterministic travel times by assuming that travel times are distributed with a mean equal to the excursion length. We prove that optimal policies in this setting follow a threshold structure and describe this structure. For the half‐line metric space we bound the performance of the randomized algorithm in the Poisson setting, and show through numerical experiments that the performance of the algorithm is often much better than this bound.     

Analysis of algorithms for two‐stage flowshops with multi‐processor task flexibility

In this article we introduce a 2‐machine flowshop with processing flexibility. Two processing modes are available for each task: namely, processing by the designated processor, and processing simultaneously by both processors. The objective studied is makespan minimization. This production environment is encountered in repetitive manufacturing shops equipped with processors that have the flexibility to execute orders either individually or in coordination. In the latter case, the product designer exploits processing synergies between two processors so as to execute a particular task much faster than a dedicated processor. This type of flowshop environment is also encountered in labor‐intensive assembly lines where products moving downstream can be processed either in the designated assembly stations or by pulling together the work teams of adjacent stations. This scheduling problem requires determining the mode of operation of each task, and the subsequent scheduling that preserves the flowshop constraints. We show that the problem is ordinary NP‐complete and obtain an optimal solution using a dynamic programming algorithm with considerable computational requirements for medium and large problems. Then, we present a number of dynamic programming relaxations and analyze their worst‐case error performance. Finally, we present a polynomial time heuristic with worst‐case error performance comparable to that of the dynamic programming relaxations. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

An FPTAS for scheduling a two‐machine flowshop with one unavailability interval

We study a deterministic two‐machine flowshop scheduling problem with an assumption that one of the two machines is not available in a specified time period. This period can be due to a breakdown, preventive maintenance, or processing unfinished jobs from a previous planning horizon. The problem is known to be NP‐hard. Pseudopolynomial dynamic programming algorithms and heuristics with worst case error bounds are given in the literature to solve the problem. They are different for the cases when the unavailability interval is for the first or second machine. The existence of a fully polynomial time approximation scheme (FPTAS) was formulated as an open conjecture in the literature. In this paper, we show that the two cases of the problem under study are equivalent to similar partition type problems. Then we derive a generic FPTAS for the latter problems with O(n⁵/ε⁴) time complexity. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

加权核范数最小化和改进小波阈值函数的图像去噪算法

针对加权核范数最小化算法存在结构残余噪声以及无法较好地保持图像边缘结构的问题,提出基于加权核范数最小化和改进小波阈值函数的图像去噪算法。利用全变分模型对噪声图像进行初步去噪,使用噪声图像与初步去噪后的图像进行差分运算,对差分后得到的噪声残差图像使用改进的小波阈值函数去噪,将小波去噪后的残差图像与初步去噪图像叠加,将叠加后的图像使用基于残余噪声水平迭代的加权核范数最小化算法进行二次去噪。相较于当下主流去噪算法,经该算法处理后的图像的PSNR和SSIM值均有所提升,能够更好地保持图像的纹理结构,且在高噪声环境下效果更佳。     

Approximation methods for the analysis of a multicomponent,multiproduct assemble‐to‐order system

In this article, we consider the performance evaluation of a multicomponent, multiproduct assemble‐to‐order (ATO) system. Each component is managed independently using a base‐stock policy at a supply facility with limited production capacity and an infinite buffer. The arrivals of demands follow a multivariate Poisson process and unfilled demands are backlogged. Because exact analysis of the proposed system is not feasible, we propose two approximation methods which provide upper and lower bounds for various performance measures such as fill rate, average waiting time, and average number of backorders of the proposed system. Our computational experiments demonstrate the effectiveness of the two approximation methods under various system settings. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Single machine scheduling with a restricted rate‐modifying activity

In this paper we consider the problem of scheduling a set of jobs on a single machine on which a rate‐modifying activity may be performed. The rate‐modifying activity is an activity that changes the production rate of the machine. So the processing time of a job is a variable, which depends on whether it is scheduled before or after the rate‐modifying activity. We assume that the rate‐modifying activity can take place only at certain predetermined time points, which is a constrained case of a similar problem discussed in the literature. The decisions under consideration are whether and when to schedule the rate‐modifying activity, and how to sequence the jobs in order to minimize some objectives. We study the problems of minimizing makespan and total completion time. We first analyze the computational complexity of both problems for most of the possible versions. The analysis shows that the problems are NP‐hard even for some special cases. Furthermore, for the NP‐hard cases of the makespan problem, we present a pseudo‐polynomial time optimal algorithm and a fully polynomial time approximation scheme. For the total completion time problem, we provide a pseudo‐polynomial time optimal algorithm for the case with agreeable modifying rates. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Many‐server loss models with non‐poisson time‐varying arrivals

This article proposes an approximation for the blocking probability in a many‐server loss model with a non‐Poisson time‐varying arrival process and flexible staffing (number of servers) and shows that it can be used to set staffing levels to stabilize the time‐varying blocking probability at a target level. Because the blocking probabilities necessarily change dramatically after each staffing change, we randomize the time of each staffing change about the planned time. We apply simulation to show that (i) the blocking probabilities cannot be stabilized without some form of randomization, (ii) the new staffing algorithm with randomiation can stabilize blocking probabilities at target levels and (iii) the required staffing can be quite different when the Poisson assumption is dropped. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 177–202, 2017     

Parallel machine scheduling with job assignment restrictions

In the classical multiprocessor scheduling problem independent jobs must be assigned to parallel, identical machines with the objective of minimizing the makespan. This article explores the effect of assignment restrictions on the jobs for multiprocessor scheduling problems. This means that each job can only be processed on a specific subset of the machines. Particular attention is given to the case of processing times restricted to one of two values, 1 and λ, differing by at most 2. A matching based polynomial time ε‐approximation algorithm is developed that has a performance ratio tending to . This algorithm is shown to have the best possible performance, tending to 3/2, for processing times 1 and 2. For the special case of nested processing sets, i.e., when the sets of machines upon which individual jobs may be assigned are non‐overlapping, the behavior of list scheduling algorithms is explored. Finally, for assignment restrictions determined by just one characteristic of the machines, such as disc storage or memory constraint in the case of high performance computing, we contribute an algorithm that provides a 3/2 worst case bound and runs in time linear in the number of jobs. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

互补问题中无SLC限制的内点算法

针对互补问题提出了一种无SLC限制的内点算法,仅要求线性函数F(x)=Hx q中的F是一个P*(τ)函数,不需要满足范数Lipschitz条件.并对该算法的全局收敛性做了证明。